package test.sort;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import lombok.Data;

public class MergeSort {
	
	private List<Integer> list = new ArrayList<>();
	
	public void add(int...nums) {
		for(int num : nums) {
			list.add(num);
		}
	}
	
	public List<SplitData> split() {
		int size = list.size();
		
		//0...size-1   (size-1)/2
		int start = 0;
		int end = size - 1;
		List<SplitData> list = split(start, end);
		return list;
	}
	
	public List<SplitData> split(int start, int end) {
		if(start==end) {
			SplitData sd = new SplitData();
			int num = list.get(start);
			List<Integer> numArray = new ArrayList<>();
			numArray.add(num);
			sd.setDatas(numArray);
			List<SplitData> sdList = new ArrayList<>();
			sdList.add(sd);
			return sdList;
		}
	
		int start1 = start;
		int end1 = start + (end - start) / 2; 
		
		
		List<SplitData> splitList1 = split(start1, end1);
		List<Integer> list1 = sort(splitList1);
//			list:start1,end1
		
		int start2 = end1 + 1;
		int end2 = end;
		
		
		List<SplitData> splitList2 = split(start2, end2);
		List<Integer> list2 = sort(splitList2);
//			list:start2,end2
		
		List<SplitData> dataList = new ArrayList<>();
		SplitData sd1 = new SplitData();
		sd1.setDatas(list1);
		SplitData sd2 = new SplitData();
		sd2.setDatas(list2);
		dataList.add(sd1);
		dataList.add(sd2);
		return dataList;
	}
	
	public List<Integer> sort(List<SplitData> splitList) {
//		System.out.println("排序=》" + splitList);
		List<Integer> sortList = new ArrayList<>();
		while(true) {
			Integer tempNum = null;
			int tempIndex = -1;
			if(splitList.size()==0) {
				break;
			}
			for(int i=0;i<splitList.size();i++) {
				SplitData data = splitList.get(i);
				List<Integer> datas = data.getDatas();
				Integer num = datas.get(data.getIndex());
				if(tempNum==null || num < tempNum) {
					tempNum = num;
					tempIndex = i;
				}
			}
			
			SplitData tempData = splitList.get(tempIndex);
			if(tempData.getDatas().size()==tempData.addIndex()) {
				splitList.remove(tempIndex);
			}
			sortList.add(tempNum);
		}
//		System.out.println("排序结果=》" + sortList);
		
		return sortList;
/*		1 7 19 
		8 12 15
		2 4 9
		
		
		*
		*/
		
	}
	
	public static void main(String[] args) {
//		SplitData sd1 = new SplitData();
//		sd1.setDatas(Arrays.asList(1,7,19));
//		
//		SplitData sd2 = new SplitData();
//		sd2.setDatas(Arrays.asList(8,12,15));
//		
//		SplitData sd3 = new SplitData();
//		sd3.setDatas(Arrays.asList(2,4,9));
//		
//		List<SplitData> list = new ArrayList<>();
//		list.add(sd1);
//		list.add(sd2);
//		list.add(sd3);
//		System.out.println(new MergeSort().sort(list));
		int array[] = new int[500];
		Random random = new Random();
		for(int i = 0;i<array.length;i++) {
			array[i] = random.nextInt(50000);
		}
		MergeSort ms = new MergeSort();
		ms.add(array);
		long l1 = System.currentTimeMillis();
		List<Integer> list = ms.sort(ms.split());
		long l2 = System.currentTimeMillis();
		System.out.println(list);
		System.out.println((l2-l1) + "ms");
		BubbleSort bs = new BubbleSort();
		bs.add(array);
		long l3 = System.currentTimeMillis();
		bs.sort();
		long l4 = System.currentTimeMillis();
		System.out.println((l4-l3) + "ms");
		System.out.println(bs.list);
	}
	
	@Data
	static class SplitData {
		private List<Integer> datas;
		private int index;
		public int addIndex() {
			return ++index;
		}
		@Override
		public String toString() {
			return "SplitData [datas=" + datas + "]";
		}
	}

}
 